Large graphs and uniqueness of their limits
Dan Kráž 

Abstract

Theory of combinatorial limits has opened new links between analysis, combinatorics, computer science, group theory and probability theory. In this theory, large dense graphs are represented by an analytic object called a graphon. Motivated by problems in extremal graph theory, we will focus on graphons that are uniquely determined
by finitely many density constraints, so-called finitely forcible graphons.

Lovasz and Szegedy initiated a systematic study of such graphons and conjectured that all such graphons must have a simple structure. On the contrary, we will show that finitely forcible graphons can contain any computable graphon as a subgraphon. Our result provides a unified framework for constructing complex finitely forcible graphons, which includes many earlier ad hoc constructions.

The talk is based on joint work with Jacob Cooper and Taisa Martins. The presentation will be self-contained and no previous knowledge of graph limits will be assumed.